The present invention relates to a device and a method for coding information and to a device and a method for decoding coded information.
It applies in particular to the transmission of information by quadrature amplitude modulation, on any transmission channel using this modulation.
Quadrature amplitude modulation of signals is well known in the communications field. According to this modulation technique, information to be transmitted has associated with it a signal of constant frequency but whose amplitude and phase represent the said information.
However, on reception, these signals may sometimes be difficult to identify when the signal has been distorted or affected by noise during transmission.
In addition, the spectrum of these signals can be relatively narrow compared with the spectrum available for transmission. This gives rise to known drawbacks. By way of example, two of these drawbacks are mentioned below:
when the energy of the signals is concentrated in a spectrum which is too narrow, these signals are easily disturbed by noise or detected and interfered with by any enemies;
for certain applications, regulations make it necessary to distribute the energy of the signals sufficiently over the entire frequency band available.
The invention intends to remedy these drawbacks by proposing a method and a device for coding information having the following advantages:
the signals are more difficult to detect and interfere with;
distribution of the energy over the available frequency band is improved;
resistance of the signals to unintentional noise is increased.
Known labeling methods associate, with the 2d points of a constellation representing the amplitude pairs used, polynomials of degree dxe2x88x921 in B, all the coefficients of which are binary, allowing the use of polynomial calculations. These methods have the drawback that the proximity between the points of the constellation, a proximity which relates to the risks of error between these points, is not well taken into account. In addition, the correction of errors in transmitting the information represented by these signals is not facilitated by these labeling methods.
The present invention intends to remedy these drawbacks.
For this purpose, according to a first aspect, the present invention relates to a device for coding information, characterized in that it has:
a first labeling means adapted to associate. with the information to be coded, K initial first degree polynomials, each of these two coefficients of the said initial polynomials being an integer number between 0 and Qxe2x88x921 inclusive.
a coding means which performs a polynomial calculation:
to form K coded sequences of a number P greater than or equal to K of coded polynomials, the first coded polynomial of each of these K sequences being equal to one of the K initial polynomials and each of the other coded polynomials of the said sequence being equal to the product of the polynomial preceding it in the sequence and a predetermined polynomial, the coefficients of the coded polynomials being calculated modulo Q and the coded polynomial being calculated modulo an irreducible second degree polynomial, and
to form a resultant sequence of P resultant polynomials respectively equal to the modulo Q sums of the coded polynomials of same rank of the K coded sequences,
a second one-to-one labeling means adapted to label the Q2 pairs of numbers representing the co-ordinates of the Q2 points of a Q2-point quadrature amplitude modulation signal constellation, with the Q2 resultant polynomials, in such a way that, if two points of the constellation have one identical co-ordinate and the other co-ordinate as close as possible, then the polynomials labeling them will have one identical coefficient and the other coefficient differing only by 1 modulo Q, and
a modulator adapted to convert each of the P resultant polynomials into a quadrature amplitude modulated signal, the amplitude pair of which is labeled by the said polynomial.
By virtue of these provisions, each of the polynomials in the sequence is associated with a pair of quadrature amplitudes, which makes it possible for the proximity between two of the pairs to correspond to a relationship between the polynomials which correspond to them.
In addition, the spectrum used for the transmission of the information is thus more spread out than the spectrum of a simple modulation of a signal.
According to a particular characteristic, the number Q is a power of a prime number.
By virtue of this provision, a decoding of the coded information can be performed using inverses of sub-matrices of the matrix used by the coding means.
According to other particular characteristics, the coding means uses a matrix having:
K lines of a number P greater than or equal to K, of elements representing polynomials in the finite ring of first degree polynomials with an integer coefficient taken modulo Q, and
at least one sub-matrix of dimensions Kxc3x97K adapted to be inverted.
By virtue of these provisions, a large number of sub-matrices have an odd determinant. Each of these odd determinants enables a decoding device to determine an estimation of the polynomials supplied by the first labeling means. The multiplication of the number of estimations which can thus be used allows a statistical decoding processing.
When the channel transmitting the coded data is subject to noise, the estimation of the representative polynomials is, thus more reliable than a simple method of statistical approximation on each demodulated polynomial.
According to other particular characteristics:
the decoding means performs the polynomial calculation by using a recursion
the first labeling means is adapted to associate with the information to be coded, K previous polynomials and then to multiply a matrix formed by these K previous polynomials by an invertible matrix of dimensions Kxc3x97K in order to produce the K initial polynomials.
By virtue of these provisions, a systematic coding can be performed, that is to say a coding in which the first resultant polynomials each represent one and only one initial polynomial.
According to a second aspect, the present invention relates to a method of coding information, characterized in that it includes:
a first labeling operation, during which K initial first degree polynomials are associated with the information to be coded, each of the two coefficients of the said initial polynomials being an integer number between 0 and Qxe2x88x921, inclusive,
a coding operation which performs a polynomial calculation:
to form K coded sequences of a number P greater than or equal to K of coded polynomials, the first coded polynomial of each of these K sequences being equal to one of the K initial polynomials and each of the other coded polynomials of the said sequence being equal to the product of the polynomial preceding it in the sequence and a predetermined polynomial, the coefficients of the coded polynomial being calculated modulo Q and the coded polynomial being calculated modulo an irreducible second degree polynomial, and
to form a resultant sequence of P resultant polynomials respectively equal to the modulo Q sums of the coded polynomials of same rank of the K coded sequences.
a second operation of one-to-one labeling of Q2 pairs of amplitudes by means of the Q2 resulting polynomials able to be formed during the coding operation, any incrementation or decrementation of one of the components, by a predetermined value, when the other remains fixed, corresponding to the incrementation by one, modulo Q, of only one of the coefficients of the resulting polynomial, the other coefficient remaining fixed,
a modulation operation, during which each of the P resulting polynomials is converted into a quadrature amplitude modulation signal where the pair of amplitudes is labeled by the said polynomial.
The invention also intends to propose a method and a device for decoding coded information which has a resistance to added noise.
To this end, according to a third aspect, the present invention relates to a device for decoding coded initial information, characterized in that it has:
a demodulator adapted to demodulate P signals modulated as the points of a quadrature amplitude modulation constellation into a demodulated sequence of P demodulated points representing a K-tuple of initial information,
a processing means adapted to:
choose K-tuples of demodulated points likely to allow calculation of the K-tuple of initial information to which they correspond,
determine, for each K-tuple of demodulated points chosen, K-tuples, referred to as xe2x80x9cneighborsxe2x80x9d, of points in the said constellation which are close to the chosen K-tuple of demodulated points,
calculate, for each K-tuple of neighboring points, the K-tuple of initial information to which it corresponds and assign to this K-tuple of initial information an affinity dependent upon the distance between the said K-tuple of neighboring points and the chosen K-tuple of demodulated points to which it is attached,
add up,
for each calculated K-tuple of initial information, or
for each item of initial information of the calculated K-tuples of initial information,
the affinities which are assigned to it, and
estimate, respectively,
the K-tuple of initial information actually coded, or
each item of initial information of the K-tuple of initial information actually coded
as being the one which has the highest sum of affinities.
According to a fourth aspect, the present invention relates to a device for decoding coded information, characterized in that it has:
a demodulator adapted to demodulate P successive quadrature amplitude modulated signals, the two components of which represent the coefficients of K polynomials of the first degree, referred to as xe2x80x9cinitial polynomialsxe2x80x9d, into a demodulated sequence of P demodulated first degree polynomials, the coefficients of same degree of the said demodulated polynomials successively representing one of the components of the corresponding demodulated signal, and
a processing means adapted to:
choose K-tuples of demodulated polynomials likely to allow calculation of the K-tuple of initial polynomials to which they correspond,
determine, for each K-tuple of demodulated polynomials chosen, K-tuples of neighboring polynomials representing K-tuples of points of the constellation close to the K-tuple of component pairs represented by the chosen K-tuple of demodulated polynomials,
calculate, for each K-tuple of neighboring polynomials, the K-tuple of initial polynomials to which it corresponds and assign to this K-tuple of initial polynomials an affinity dependent upon the distance between the said K-tuple of points represented by the K-tuple of neighboring polynomials and the K-tuple of component pairs represented by the chosen K-tuple of demodulated polynomials to which it is attached,
add up,
for each calculated K-tuple of initial polynomials or
for each initial polynomial of the calculated K-tuples of initial polynomials,
the affinities which are assigned to it, and
estimate, respectively,
the K-tuple of initial polynomials actually coded or
each initial polynomial of the K-tuple of initial polynomials, actually coded
as being the one which has the highest sum of affinities.
By virtue of these provisions, each point or polynomial of the demodulated sequence is associated with neighboring points or polynomials which have a high probability of corresponding to the initial information, according to known laws on noise affecting signals modulated by quadrature amplitude modulation: for a Gaussian channel, the risk of confusion is related to the distance between neighboring points of the constellation and the proximity between two demodulated quadrature component pairs corresponds to a high probability of confusion between the modulated signals from which they originate.
Thus, the invention makes it possible to decode coded information by:
a coding means which performs a polynomial calculation:
to form K coded sequences of a number P greater than or equal to K of coded polynomials, the first coded polynomial of each of these K sequences being equal to one of the K initial polynomials and each of the other coded polynomials of the said sequence being equal to the product of the polynomial preceding it in the sequence and a predetermined polynomial, and
to form a resultant sequence of P resultant polynomials respectively equal to the modulo Q sums of the coded polynomials of same rank of the K coded sequences,
a second one-to-one labeling means adapted to label the Q2 pairs of numbers representing the coordinates of the Q2 points of a Q2-point quadrature amplitude modulation signal constellation, with the Q2 resultant polynomials, in such a way that, if two points of the constellation have one identical coordinate and the other coordinate as close as possible, then the polynomials labeling them will have one identical coefficient and the other coefficient differing only by 1 modulo Q, and
a modulator adapted to convert each of the P resultant polynomials into a quadrature amplitude modulated signal, the amplitude pair of which is labeled by the said polynomial.
The device according to the invention, by comparison with the devices using the maximum probability method which consists of performing a correlation between all the code words and what has been received, has a simpler construction and faster operation while having comparable performance.
According to particular characteristics, the processing means is adapted to assign to each K-tuple of initial polynomials an affinity decreasing as a function of the distance between the K-tuple of points represented by the K-tuple of neighboring polynomials and the K-tuple of component pairs represented by the chosen K-tuple of demodulated polynomials to which it is attached.
By virtue of these provisions, the summed affinities each represent the probability that the K-tuple of neighboring polynomials considered is the K-tuple of initial polynomials which is at the origin of the K-tuple of demodulated polynomials.
According to a fifth aspect, the present invention relates to a method of decoding coded initial information, characterized in that it consists of:
a demodulation operation, during which P signals modulated as the points of a quadrature amplitude modulation constellation are demodulated into a demodulated sequence of P demodulated points representing a K-tuple of initial information,
a processing phase consisting of:
a selection operation, during which K-tuples of demodulated points likely to allow calculation of the K-tuple of initial information to which they correspond are chosen,
a determination operation during which, for each of the chosen K-tuples of demodulated points, K-tuples, referred to as xe2x80x9cneighborsxe2x80x9d, of points in the said constellation which are close to the chosen K-tuple of demodulated points are determined,
a calculation operation during which, for each K-tuple of neighboring points, the K-tuple of initial information to which it corresponds is calculated and this K-tuple of initial information is assigned an affinity dependent upon the distance between the said K-tuple of neighboring points and the chosen K-tuple of demodulated points to which it is attached,
a summation operation during which,
for each calculated K-tuple of initial information, or
for each item of initial information of the calculated K-tuples of initial information,
the affinities which are assigned to it are summed, and
an estimation operation during which, respectively,
the K-tuple of initial information actually coded, or
each item of initial information of the K-tuple of initial information, actually coded
is estimated as being the one which has the highest sum of affinities.
According to a sixth aspect, the present invention relates to a method of decoding coded information, characterized in that it consists of:
a demodulation operation during which P successive quadrature amplitude modulated signals are demodulated, the two components of which represent the coefficients of K polynomials of the first degree referred to as xe2x80x9cinitial polynomialsxe2x80x9d, into a demodulated sequence of P demodulated first degree polynomials, the coefficients of same degree of the said demodulated polynomials successively representing one of the components of the corresponding demodulated signal, and
a processing phase consisting of:
a selection operation during which K-tuples of demodulated polynomials likely to allow calculation of the K-tuple of initial polynomials to which they correspond are chosen,
a determination operation during which, for each of the chosen K-tuples of demodulated polynomials, K-tuples of neighboring polynomials are determined, representing K-tuples of points of the constellation close to the K-tuple of component pairs represented by the chosen K-tuple of demodulated polynomials,
a calculation operation, during which, for each K-tuple of neighboring polynomials, the K-tuple of initial polynomials to which it corresponds is calculated and this K-tuple of initial polynomials is assigned an affinity dependent upon the distance between the K-tuple of points represented by the said K-tuple of neighboring polynomials and the K-tuple of component pairs represented by the chosen K-tuple of demodulated polynomials to which it is attached,
a summation operation, during which,
for each calculated K-tuple of initial polynomials or
for each initial polynomial of the calculated K-tuples of initial polynomials,
the affinities which are assigned to it are added up, and
an estimation operation, during which, respectively,
the K-tuple of initial polynomials actually coded or
each initial polynomial of the K-tuple of initial polynomials actually coded
is estimated as being the one which has the highest sum of affinities.
The invention also relates to a computer, a facsimile machine, an information processing system, an information capture system (such as a video camera, a digital camera, a scanner, a copier, etc.) and an information reproduction system (such as a printer, a copier, etc.), characterized in that they have:
an information coding device as briefly disclosed above, or
an information decoding device as briefly disclosed above, and a microprocessor system adapted to implement the method as briefly disclosed above.
The present invention also concerns a storage medium, or memory, such as a floppy disk or a CD-ROM, for storing thereon instructions which, when executed by a processor, cause the processor to implement the method as briefly disclosed above.
Since this method and these devices have the same advantages as the devices briefly disclosed above, these are not repeated here.